package com.note.feng.dataStructureAlgorithm.linked;

/**
 * 链表的特征：
 *  链表（linked list）是一种真正的动态的数据结构。
 *  链表是一种线性表，但是不会按线性的顺序存储数据，而是在每一个结点里存到下一个结点的指针。
 *  使用链表结构可以克服数组需要预先知道数组大小的缺点，但增加了结点的指针域，空间开销比较大。
 *  链表允许插入和移除链表上任意位置上的结点，但是不允许随机访问。
 *  链表有很多种不同的类型：单向链表、双向链表以及循环链表。
 *
 * 单链表的定义：
 *  链表中的数据是以节点来表示的。
 *  每个结点的构成：元素 + 指针。
 *  元素就是存放数据的存储单元，指针就是连接每个结点的地址数据。
 *  以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。
 * @param <E>
 */
public class SingleLinkedList <E> {
    //虚拟头结点
    private Node dummyHead;
    private int size;

    public SingleLinkedList(){
        this.dummyHead = new Node();
        this.size = 0;
    }
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }
    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new RuntimeException("failed, index can not < 0 or > size");
        }
        //找到index的前置结点
        Node prev = dummyHead;
        for(int i = 0; i < index; i ++){
            prev = prev.next;
        }
//        Node node = new Node(e);
//        node.next = prev.next;
//        prev.next = node;
        //上面3行和下面1行结果一样，提现出了构造函数的重要性
        prev.next = new Node(e, prev.next);

        size ++;
    }
    public void addFrist(E e){
        add(0, e);
    }
    public void addLast(E e){
        add(size, e);
    }
    public E get(int index){
        if(index < 0 || index > size){
            throw new RuntimeException("failed, index can not < 0 or > size");
        }
        Node node = dummyHead;
        for(int i = 0; i < index; i ++){
            node = node.next;
        }
        return node.next.e;
    }
    public E getFrist(){
        return get(0);
    }
    public E getLast(){
        return get(size - 1);
    }
    public boolean contains(E e){
        Node node = dummyHead.next;
        while(node != null){
            if(node.e.equals(e)){
                return true;
            }
            node = node.next;
        }
        return false;
    }
    public void set(int index, E e){
        if(index < 0 || index > size){
            throw new RuntimeException("failed, index can not < 0 or > size");
        }
        Node prev = dummyHead;
        for(int i = 0; i < index; i ++){
            prev = prev.next;
        }
        prev.next.e = e;
    }

    public E remove(int index){
        if(index < 0 || index > size){
            throw new RuntimeException("failed, index can not < 0 or > size");
        }
        Node node = dummyHead;
        for(int i = 0; i < index; i ++){
            node = node.next;
        }
        Node delNode = node.next;
        node.next = delNode.next;
        size --;
        delNode.next = null;
        return delNode.e;
    }

    public E removeFrist(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size - 1);
    }

    public void removeElement(E e){
        Node node = dummyHead;
        while(node.next != null){
            if(node.next.e.equals(e)){
                break;
            }
            node = node.next;
        }
        if(node.next != null){
            Node delNode = node.next;
            node.next = delNode.next;
            size --;
            delNode = null;
        }
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node node = dummyHead.next;
        for(int i = 0; i < size; i ++){
            sb.append(node.e);
            if(i != size - 1){
                sb.append(",");
            }
            node = node.next;
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        SingleLinkedList<Integer> linked = new SingleLinkedList<>();
        for(int i = 0; i < 10; i ++){
            linked.addLast(i);
            System.out.println(linked);
            if(i % 3 == 2){
                linked.removeFrist();
                System.out.println(linked);
            }
        }
    }

    private class Node{
        public E e;
        public Node next;

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }
        public Node(E e){
            this.e = e;
            this.next = null;
        }
        public Node(){
            this.e = null;
            this.next = null;
        }

        public String toString(){
            return e.toString();
        }
    }
}
